package momo.multitree.util;

import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.Vector;

import momo.multitree.structure.Edge;
import momo.multitree.structure.Graph;
import momo.multitree.structure.Node;
import momo.multitree.structure.Tree;

public class CompactAlgo implements SpanTreeGenerator
{
	private HashMap<Edge, Vector<Edge>> candi;
	private Vector<Edge> leave;
	private Vector<Edge> edgesOfInitTree;
	private Vector<Edge> leftEdges;
	private HashMap<Node, Integer> nodeID;
	private Graph initTree;
	
	private int TEST_COUNTER = 0;
	
	public CompactAlgo()
	{
		candi = new HashMap<Edge, Vector<Edge>>();
		leave = new Vector<Edge>();
		edgesOfInitTree = new Vector<Edge>();
		leftEdges = new Vector<Edge>();
		nodeID = new HashMap<Node, Integer>();
		initTree = new Graph();
	}
	
	public Collection<Tree> enumerateAllSpanningTree(Graph graph)
	{
		return Collections.unmodifiableCollection(convertAllToTrees(generateAllSpanningGraph(graph)));
	}
	
	public Collection<Graph> generateAllSpanningGraph(Graph graph)
	{
		Collection<Graph> graphs = new LinkedHashSet<Graph>();
		if ( graph.isConnectedGraph() )
		{
			initDFS(graph);
			initCandi();
			initLeave();
			printInitSetting();
			graphs.add(initTree);
			findChildren(candi, initTree, graphs);
		}
		System.out.println("Total Tree in CompactAlgo: " + graphs.size());
		return Collections.unmodifiableCollection(graphs);
	}
	
	private void findChildren(HashMap<Edge, Vector<Edge>> currCandi, Graph graph, Collection<Graph> trees)
	{
		// if leave = 0 then return;
		if ( leave.isEmpty() )
		{
//			System.out.println("No children found at COUNTER: " + TEST_COUNTER);
			return;
		}
		
		
		int TMP_COUNTER = ++TEST_COUNTER;
		System.out.println("~~~~~~~~~~~~~~~~~~~ START COUNTER: " + TMP_COUNTER);
//		printStats(currCandi);
		
		//init tmpCandi
		HashMap<Edge, Vector<Edge>> tmpCandi = new HashMap<Edge, Vector<Edge>>();
		// init local Q
		Vector<Edge> Q = new Vector<Edge>();
		// ek = last entry of leave
		Edge ek = leave.lastElement();
		
		// delete ek from leave
		leave.remove(ek);
		
		int counter = 0;
		// while  candi (ek) != 0 begin
		Vector<Edge> candiOfEk = currCandi.get(ek);
		while ( !candiOfEk.isEmpty() )
		{
//			System.out.println("while loop of " + (++counter) + " at Counter: " + TMP_COUNTER); 
			// g = last entry of candi(ek);
			Edge g = candiOfEk.lastElement();
			// delete g from candi(ek) 
			candiOfEk.remove(g);
			// add g to head of Q
			Q.add(0, g);
			// output ( -ek, +g, tree );
//			System.out.println("@@@@@@@@@@@@@@@@ - ek: " + ek.getId()+", + g: " + g.getId());
			Graph newGraph = createSpanningGraph(graph, ek, g);
//			trees.add(newGraph);
//			trees.addAll( convertToTrees(newGraph) );
//			printStats(currCandi);
			//backup candi
			backup(currCandi, tmpCandi);
//			System.out.println("############ Tmp Candi ############");
//			printStats(tmpCandi);
			// update DS( ek, g );
			updateDataStructure(currCandi, ek, g);
			// findChildren();
//			System.out.println("^^^^^^^^ Finding children");
			findChildren(currCandi, newGraph, trees);
			// restore DS (ek, g );
//			System.out.println("############ COUNTER: " +TMP_COUNTER+ " Tmp Candi  after find Children in while loop############");
//			printStats(tmpCandi);
			backup(tmpCandi, currCandi);
//			printStats(currCandi);
		}
		// move all entries of Q to candi(ek)
//		System.out.println("END while loop of Counter: " + TMP_COUNTER);
		candiOfEk.addAll(Q);
//		printStats(currCandi);
		
		
		//backup candi
		backup(currCandi, tmpCandi);
		// update DS( ek, ek );
		updateDataStructure(currCandi, ek, ek);
		// findChildren();
//		System.out.println("^^^^^^^^ Finding brothers");
		findChildren(currCandi, graph, trees);
		// restore DS (ek, ek );
		backup(tmpCandi, currCandi);
		// add ek to the end of leave;
//		if ( !leave.contains(ek) )
			leave.add(ek);
		
//		printStats(currCandi);
		
//		System.out.println("~~~~~~~~~~~~~~~~~~~ END COUNTER: " + TMP_COUNTER);
	}
	
	private Graph createSpanningGraph(Graph graph, Edge removal, Edge add)
	{
		Graph g = new Graph(graph);
		g.remove(removal);
		g.add(add);
		return g;
	}
	
	private Collection<Tree> convertAllToTrees(Collection<Graph> graphs)
	{
		Collection<Tree> trees = new LinkedHashSet<Tree>();
		Iterator<Graph> iterGraph = graphs.iterator();
		while ( iterGraph.hasNext() )
		{
			Graph g = iterGraph.next();
			Set<Node> set = g.getNodes();
			Iterator<Node> iter = set.iterator();
			while ( iter.hasNext() )
			{
				Node root = iter.next();
//				trees.add(Tree.graphToTree(root, g));
				trees.add(new Tree(root, g));
			}
		}
		return Collections.unmodifiableCollection(trees);
	}
	
	private void updateDataStructure(HashMap<Edge, Vector<Edge>> tmpCandi, Edge ek, Edge g)
	{
		Edge et = null;
		// et = the edge in initTree with -et = +g if exists, otherwise return 
		for(Edge edge: edgesOfInitTree)
			if ( nodeID.get(edge.getTailNode()) == nodeID.get(g.getHeadNode()) )
				et = edge;
		if ( et == null )
		{
//			System.out.println("ET is null");
			return;
		}
		
//		System.out.println("Ek: " + ek.getId());
//		System.out.println("g: " + g.getId());
//		System.out.println("Et: " + et.getId());
		// move {e of candi(ek) | +e < +g} from candi(ek) to candi(et);
		Vector<Edge> candiOfEk = tmpCandi.get(ek);
		Vector<Edge> candiOfEt = tmpCandi.get(et);
		
		boolean	wasEmpty = candiOfEt.isEmpty();
		
		int size = candiOfEk.size();
		int counter = 0;
		while ( !candiOfEk.isEmpty() && counter < size )
		{
			Edge edge = candiOfEk.firstElement();
			counter ++;
			if ( nodeID.get(edge.getHeadNode()) < nodeID.get(g.getHeadNode()) )
			{
				candiOfEt.add(edge);
				candiOfEk.remove(edge);
			}
		}
		
		// if candi(et) changes from empty to nonempty, insert et into leave;
		if ( wasEmpty && !candiOfEt.isEmpty() )
			if ( !leave.contains(et) )
				leave.add(0, et);
	}
	
	private void backup(HashMap<Edge, Vector<Edge>> from, HashMap<Edge, Vector<Edge>> to)
	{
		Set<Edge> keySet = from.keySet();
		Iterator<Edge> iterKey = keySet.iterator();
		while ( iterKey.hasNext() )
		{
			Edge key = iterKey.next();
			Vector<Edge> vecFrom = from.get(key);
			Vector<Edge> vecTo = to.get(key);
			if ( vecTo == null )
				vecTo = new Vector<Edge>();
			if ( vecFrom == null )
				vecFrom = new Vector<Edge>();
			
			vecTo.removeAllElements();
			vecTo.addAll(vecFrom);
			to.put(key, vecTo);
		}
	}
	
	private void initDFS(Graph graph)
	{
		int counter = 1;
		HashSet<Node> visited = new HashSet<Node>();
		HashSet<Edge> edgeVisited = new HashSet<Edge>();
		
		Node[] nodes = graph.getNodes().toArray(new Node[0]);
		Node root = nodes[0];
		
		visited.add(root);
		
		
		nodeID.put(root, counter);
		
		initDFS(graph, visited, null, root, counter);
	}
	
	private void initDFS(Graph graph, HashSet<Node> visited, Node parent, Node currNode, int counter)
	{
		visited.add(currNode);
		
		Set<Edge> set = graph.getEdgesOfNode(currNode);
		Iterator<Edge> iter = set.iterator();
		while ( iter.hasNext() )
		{
			Edge edge = iter.next();
			Node toNode = edge.nextNode(currNode);
			
			if ( !visited.contains(toNode) )
			{
				//add to T_0 tree;
				edge.swap(currNode);
				edgesOfInitTree.add(edge);
				initTree.add(edge);
				nodeID.put(toNode, ++counter);
				initDFS(graph, visited, currNode, toNode, counter);
			}else if ( toNode != parent )
			{
				if ( !leftEdges.contains(edge) )
				{
					edge.swap(toNode);
					leftEdges.add(edge);
				}
			}
		}
	}
	
	private void initCandi()
	{
		for(Edge edgeInTree: edgesOfInitTree)
		{
			Vector<Edge> initVec = new Vector<Edge>();
			candi.put(edgeInTree, initVec);
			for(Edge edgeNotInTree: leftEdges)
			{
				if ( nodeID.get(edgeNotInTree.getHeadNode()) <= nodeID.get(edgeInTree.getHeadNode()) 
						&& nodeID.get(edgeNotInTree.getTailNode()) == nodeID.get(edgeInTree.getTailNode()) )
				{
					Vector<Edge> vec = candi.get(edgeInTree);
					vec.add(edgeNotInTree);
					candi.put(edgeInTree, vec);
				}
						
			}
		}
	}
	
	private void initLeave()
	{
		for(Edge edgeInTree: edgesOfInitTree)
		{
			Vector<Edge> vec = candi.get(edgeInTree); 
			if ( vec.size() > 0 )
				leave.add(edgeInTree);
		}
	}
	
	public void printInitSetting()
	{
		System.out.println("~~~ Init Tree ~~~");
		for(Edge edge: edgesOfInitTree)
			System.out.println(" = " + edge.toString());
		
		System.out.println("\n~~~ Edges Not in Init Tree ~~~");
		for(Edge edge: leftEdges)
			System.out.println(" = " + edge.toString());
		
		System.out.println("\n~~~ Node Id ~~~");
		for(Edge edge: edgesOfInitTree)
		{
			System.out.println("Edge ID: " + edge.getId());
			System.out.println(" + :" + nodeID.get(edge.getHeadNode()) );
			System.out.println(" - :" + nodeID.get(edge.getTailNode()) );
		}
		for(Edge edge: leftEdges)
		{
			System.out.println("Edge ID: " + edge.getId());
			System.out.println(" + :" + nodeID.get(edge.getHeadNode()) );
			System.out.println(" - :" + nodeID.get(edge.getTailNode()) );
		}
		printStats(candi);
	}
	
	public void printStats(HashMap<Edge, Vector<Edge>> tmpCandi)
	{
		boolean test = true;
		if ( test )
		{
			System.out.println("\n~~~ Candi ~~~");
			for(Edge edge: edgesOfInitTree)
			{
				Vector<Edge> vec = tmpCandi.get(edge);
				System.out.print(edge.getId()+": ");
				if ( vec == null )
					System.out.print(" ## (null set)\n");
				else
				{
					if ( vec.isEmpty() )
						System.out.print("\n");
					for(Edge e: vec)
						System.out.print(" (" + e.getId()+")\n");
				}
			}
			printLeave();
		}
	}
	
	public void printLeave()
	{
		System.out.println("\n~~~ Leave ~~~");
		for(Edge edge: leave)
			System.out.println(" = " + edge.getId());
		System.out.println("");
	}
	
}//end of class TreeEnumerator
